110. Balanced Binary Tree

Easy

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

  3
 / \
9  20
  /  \
 15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Return false.

虽然简单，但仍然不能小看的一道题。判断一棵树是否是平衡二叉树，平衡二叉树定义如下：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

1. 递归+递归

   最外面的递归用来判断一棵树和他的子树是不是平衡二叉树，最里面的递归用来计算左右子树的高度(采用回溯方法计算高度)

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root: return True
        right = self.getDepth(root.right)
        left = self.getDepth(root.left)
        if abs(right - left) > 1:
            return False
        else:
            return self.isBalanced(root.right) and self.isBalanced(root.left)
        
    def getDepth(self, node):
        if not node:
            return 0
        else:
            right = self.getDepth(node.right)
            left = self.getDepth(node.left)
            return max(right, left) + 1